Many conventional search engine systems typically include one or more search engine devices. A search engine device can include circuitry for performing one or more types of search operations. In a search operation, a comparand (or key) may be compared to multiple entries to see if all or a portion of the key matches an entry. After a search operation, a search engine may give a search result as an output. Typically a search result may include an “index” value, which may be used to access associated data or as associated data itself.
Search engine devices may take a variety of forms. As but a few of the possible examples, some search engine devices are based on particular types of content addressable memory (CAM) cells. Such CAM cells may include storage circuits integrated with compare circuits. An example of storage circuits may be static random access memory (SRAM) type cells or dynamic random access memory (DRAM) type cells. Alternate approaches to search engines may include random access memories (RAM) arrays, or the like, with separate matching circuits and/or processes.
A CAM may perform the matching functions described above by providing the ability to apply a search key or “comparand” to a table of stored data values. A CAM may then determine if any of the data values matches a given search key. A typical conventional search operation, along with a general architecture of a conventional CAM system will now be described in more detail.
Referring to FIG. 10A, an example of a conventional CAM system is designated by the general reference number 1000. A conventional CAM system 1000 may include a network processor (NPU) 1002, and a number of CAM devices 1004-1 and 1004-2 that may be connected by control and data links or buses 1008.
Referring now to FIG. 10B, an example of a CAM device 1004 is shown in more detail, and may include a CAM array 1012, CAM control circuits 1014, and register sets 1015. Register sets 1015 may include a comparand register (CMPR) set 1016 and a mask register set 1018.
A CAM array 1012 may contain any number of CAM storage cells. Data may be written to and/or read from such CAM storage cells. A CAM array 1012 may also support a search function, where a search key or “comparand” may be compared against data stored in any number of CAM entries. If the data of any CAM entry matches a comparand value, then a search hit may be indicated. Otherwise a search miss may be indicated.
CAM control circuits 1014 can take CAM control and data signals 1008 as inputs and generate signals for controlling the operation of a CAM array 1012.
A CMPR set 1016 may include storage locations for storing comparand values used for search operations. In the particular example of FIG. 10B, a CMPR set 1016 includes eight storage locations. Comparand values may be loaded into a location of a CMPR set 1016 by CAM control and data signals 1008. Comparand values may be saved within a CMPR set 1016 during a search. Such a saved comparand value may then be used in a subsequent search without an NPU, or the like, having to re-transmit the comparand value.
A mask register set 1018 may store a number of mask values that may be used in a compare operation. As is well understood, a mask value can mask selected bits of a comparand from a compare operation. Typically, one type of mask bit value indicates a mask operation, while another indicates a no-mask operation. More particularly, if a masking bit value is “1” a mask value of “0000 1111” would mask the first four bits of comparand from a compare operation, and include the last four bits in the compare operation.
Within a mask register set 1018, mask values may be stored at particular addressable register locations. Thus, particular mask values may be accessed by a mask register set address. Thus, a search operation may designate a mask register set address value rather than supply an entire mask value.
Having described an example of a CAM based system, as well as a CAM block, a conventional CAM search operation will now be described with reference to FIGS. 10A and 10B. To perform a search operation, an NPU 1002 may provide to a CAM device (1004-1 and 1004-2) a comparand value, a mask register address value within mask register set 1018, as well as the location within a comparand register set 1016 to store the comparand data. In this example, it will be assumed that a mask register address value of “0” is provided.
A mask value located at address 0 in a mask register set 1018 may be accessed for a compare operation. Such a mask value may then a mask a comparand value in a compare operation. Such masking may occur in a variety of ways. As but one example, for each non-masked bit, complementary comparand bit lines may be driven to opposite logic levels. In contrast, for each masked bit, complementary comparand bit lines may be driven to a same logic levels. Such comparand bit lines may then be applied to CAM storage locations within a CAM array 1012.
If any of the values stored in a CAM array 1012 matches the masked comparand value, a search operation can generate a search “hit.” Various actions may be taken in response to a search hit. As one example, an index value may be generated for the CAM storage location that matches a comparand value. Further, a search result may be communicated back to a NPU 1002 as a RESULT. It is noted that in a conventional case, a comparand register 1016 location corresponding to a matching comparand value may then be free for use.
Referring now to FIG. 11, a conventional mask register set 1100 is set forth. A mask register set 1100 may include a set of registers that can store various mask values. Registers within a register set may be accessed by a register address. In the very particular example of FIG. 11, a mask register set 1100 may contain a set of registers accessible by address values 0-15.
Conventionally, the number of available registers in a CAM block may be limited. In the example of FIG. 11, a single set of 16 registers may be included. Such a set of 16 registers may have a predetermined width (e.g., 72-bits).
If a mask value having a width greater than a mask register location is needed, multiple register locations may be utilized. For example, referring to FIG. 11, a 144-bit search may utilize register location pairs. A 288-bit search may utilize four 72-bit register locations. Similarly, a 576-bit search may utilize eight register locations.
While conventional mask register sets may store mask values for re-use, such conventional approaches can have drawbacks. As noted above, when a stored mask value has a width greater than one register, multiple register locations may be used to store a mask (e.g., 2 72-bit locations may store a 144-bit mask value). However, a command issuing device, such as an NPU may have to maintain a record of which mask register index values are associated with one another. It would be desirable to remove this burden of tracking the state of the registers in register sets by an NPU, or the like.